package Simple3;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertSame;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import junit.framework.Assert;

import org.junit.Test;

public class oct {
	public static boolean isUniqueChars2(String str) {
		boolean[] char_set = new boolean[256];
		for (int i = 0; i < str.length(); i++) {
			int val = str.charAt(i);
			if (char_set[val])
				return false;
			char_set[val] = true;
		}
		return true;
	}

	public static boolean isUniqueChars(String str) {
		int checker = 0;
		for (int i = 0; i < str.length(); ++i) {
			int val = str.charAt(i) - 'a';
			if ((checker & (1 << val)) > 0)
				return false;
			checker |= (1 << val);
		}
		return true;
	}

	private int LeastCommonMultiple(int a, int b) {
		int m = GreatestCommonDivisor(a, b);
		int n = a * b / m;
		return n;
	}

	public int GreatestCommonDivisor(int x, int y) {
		int temp;
		if (x < y) {
			temp = x;
			x = y;
			y = temp;
		}
		while (y != 0) {
			if (x == y)
				return 1;
			else {
				int k = x % y;
				x = y;
				y = k;
			}
		}
		return x;
	}

	public static boolean checkPowerOfTwo(long i) {

		return i > 0 && (((i - 1) & i) == 0);
	}

	public static boolean checkPowerOfTwo2(int a) {
		if (a <= 0) {
			return false;
		}
		String k = Integer.toBinaryString(a);

		char[] arr = k.toCharArray();
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == '1') {
				count++;
			}
		}
		return count == 1;
	}

	public static String getDecimal(byte[] array) {	
		List<Integer> arr = new ArrayList<Integer>();
		for (;;) {
			int m = 0;
			boolean allZero = true;
			for (int i = 0; i < array.length; i++) {
				int x = m * 256 + (array[i] & 0xFF);//
				m = x % 10;
				array[i] = (byte) (x / 10);
				if (array[i] != 0) {
					allZero = false;
				}
			}
			arr.add(m);
			if (allZero) {
				break;
			}
		}
		//int array to char array.
		char[] charArray = new char[arr.size()];
		for (int i = 0; i < arr.size(); i++) {
			charArray[i] = (char) ('0' + (int) arr.get(arr.size()-i-1));//int 0-9 to asc char.
		}
		return new String(charArray);
	}
    
	@Test
	public void testgetDecimal() {
		assertEquals("1099511627775",getDecimal(new byte[] {(byte) 255,(byte) 255,(byte) 255,(byte) 255, (byte) 255}));
		assertEquals("0", getDecimal(new byte[] { (byte) 0 }));
		assertEquals("255", getDecimal(new byte[] { (byte) 255 }));
		assertEquals("65535", getDecimal(new byte[] { (byte) 255, (byte) 255 }));
		
	}

	public static void reverseWords(char[] s) {
		swap(s, 0, s.length - 1);
		for (int i = 0; i < s.length;) {
			while (i < s.length && s[i] == ' ') {
				i++;
			}
			int start = i;
			while (i < s.length && s[i] != ' ') {
				i++;
			}
			swap(s, start, i - 1);
		}
	}

	public static void swap(char[] arr, int start, int end) {

		for (int i = start, j = end; i < j; i++, j--) {
			char temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
		}
	}

	public static int getNumberOfPaths(int n, int m, int[][] arr) {
		int[] p = new int[n];
		int temp = 1;
		for (int i = 0; i < n; i++) {
			if (arr[i][0] == 1) {
				temp = 0;
			}
			p[i] = temp;
		}
		for (int j = 1; j < m; j++) {
			int sum = 0;
			for (int i = 0; i < n; i++) {
				if (arr[i][j] == 1) {
					sum = 0;
				} else {
					sum = sum + p[i];
				}
				p[i] = sum;
			}
		}
		return p[n - 1];
	}

	public static int removeConsecutiveDuplication(char[] arr) {
		int i;// What if not consecutive?
		int j;
		if (arr.length == 0) {
			return 0;
		}
		if (arr.length == 1) {
			System.out.println(arr[0]);
			return 1;
		}
		for (i = 0, j = 1; j < arr.length;) {
			if (arr[i] == arr[j]) {
				j++;
			} else {
				arr[i + 1] = arr[j];
				j++;
				i++;
			}
		}
		char[] B = Arrays.copyOfRange(arr, 0, i + 1);
		System.out.println(Arrays.toString(B));// How not to new
												// a new array here(do this in
												// place).see next code
		return i + 1;
	}

	public static int removeDuplicatesShowOnlyOnce2(int[] A) {
		int count = 0;
		for (int i = 1; i < A.length; i++) {
			if (A[i] == A[i - 1]) { // skip duplicates
				count++;
			} else if (count > 0) { // copy over non-duplicates
				A[i - count] = A[i];
			}
		}
		System.out.print(Arrays.toString(A));
		return A.length - count;
	}

	public static int removeDuplicatesAndCanDuplicateTwice(int[] A) {
		int count = 0;
		for (int i = 2; i < A.length; ++i) {
			if (A[i] == A[i - count - 1] && A[i] == A[i - count - 2]) { // skip
																		// duplicates
				++count;
			} else if (count > 0) { // copy over non-duplicates
				A[i - count] = A[i];
			}
		}
		return A.length - count;
	}

	public void twoSum(int[] numbers, int target) {
		for (int i = 0; i < numbers.length; i++) {
			for (int j = 0; j < numbers.length; j++) {
				if (numbers[i] == numbers[j]) {
					System.out.format("index1=  ,index2= ", i, j);
				}
			}
		}
	}

	/*
	 * public static void main(String[] args) { Random r = new Random();
	 * String[][] x = new String[10][];
	 * 
	 * for(int row=0 ; row< x.length; row++){ int size = r.nextInt(10); x[row] =
	 * new String[size];
	 * 
	 * for(int col=0; col < x[row].length; col++){ x[row][col] = "["+ row + ","
	 * + col + "]"; } System.out.println(); } for(int row=0 ; row< x.length;
	 * row++){ for(int col=0; col < x[row].length; col++){
	 * System.out.print(x[row][col] + "\t"); } System.out.println(); } }
	 */
	private static String HowmanyConsecutiveDuplication(String s) {// ???
		int count = 1;
		int i, j;
		StringBuilder sb = new StringBuilder();
		for (i = 0, j = 1; j < s.length();) {
			if (s.charAt(i) == s.charAt(j)) {
				count++;
				j++;
			} else {
				sb.append(s.charAt(i));
				sb.append(count);
				i = i + count;
				j++;
				count = 1;
			}
		}
		sb.append(s.charAt(i));
		sb.append(count);
		return sb.toString();
	}

	// @Test
	public void testManyConsecutiveDuplication() {
		assertEquals("f1g3l1u3j1", HowmanyConsecutiveDuplication("fgggluuuj"));
	}

	// @Test
	public void testRemoveConsecutiveDuplication() {
		char[] arr = "abbbbcccccddd".toCharArray();
		int len = removeConsecutiveDuplication(arr);
		assertEquals("abcd", new String(Arrays.copyOfRange(arr, 0, len)));
	}

	public static int getNumberofShortestPath(int n, int m, int[][] matrix) {
		int[] numberofShortestPath = getNumberofShortestPath(n, m, 0, 0, matrix);
		return numberofShortestPath[1];
	}

	public static int[] getNumberofShortestPath(int n, int m, int row, int col,
			int[][] matrix) {
		if (row == n - 1 && col == m - 1) {
			return new int[] { 0, 1 };
		}
		int numberOfPath = 0;
		int lengthOfPath = Integer.MAX_VALUE;
		int[][] direction = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
		int[] result = { lengthOfPath, numberOfPath };
		matrix[row][col] = 1;
		for (int i = 0; i < direction.length; i++) {
			int newrow = row + direction[i][0];
			int newcol = col + direction[i][1];
			if (newrow < n && newrow >= 0 && newcol < m && newcol >= 0
					&& matrix[newrow][newcol] == 0) {

				result = getNumberofShortestPath(n, m, newrow, newcol, matrix);
				if (result[0] < lengthOfPath) {
					lengthOfPath = result[0];
					numberOfPath = result[1];
				} else if (result[0] == lengthOfPath) {
					lengthOfPath = result[0];
					numberOfPath = numberOfPath + result[1];
				}
			}
		}
		matrix[row][col] = 0;
		if (lengthOfPath != Integer.MAX_VALUE) {
			result[0] = lengthOfPath + 1;
		} else {
			result[0] = lengthOfPath;
		}
		result[1] = numberOfPath;
		return result;
	}

	// @Test
	public void testPowerOfTwo() {
		Assert.assertFalse(checkPowerOfTwo(-1));
		Assert.assertTrue(checkPowerOfTwo(2));
		Assert.assertTrue(checkPowerOfTwo(4));
		// Assert.assertFalse(checkPowerOfTwo(1<<31 -1));
		Assert.assertFalse(checkPowerOfTwo(0));

	}

	// @Test
	public void testReverseWord() {

		char[] s1 = "I love you".toCharArray();
		reverseWords(s1);
		assertEquals("you love I", new String(s1));
		char[] s2 = "I love   you".toCharArray();
		reverseWords(s2);
		assertEquals("you   love I", new String(s2));
	}

	// @Test
	public void getNumbeofPath() {

		// 0 0

		// 0 0

		assertSame(2,
				getNumberOfPaths(2, 2, new int[][] { { 0, 0 }, { 0, 0 } }));

		// 0 0

		// 1 0

		// 0 0

		assertSame(
				1,
				getNumberOfPaths(3, 2, new int[][] { { 0, 0 }, { 1, 0 },
						{ 0, 0 } }));

		// 0 0 0

		// 0 0 0

		// 0 0 0

		assertSame(
				6,
				getNumberOfPaths(3, 3, new int[][] { { 0, 0, 0 }, { 0, 0, 0 },
						{ 0, 0, 0 } }));

		// 0 0 0

		// 0 1 0

		// 0 0 0

		assertSame(
				2,
				getNumberOfPaths(3, 3, new int[][] { { 0, 0, 0 }, { 0, 1, 0 },
						{ 0, 0, 0 } }));

		// 0 0 0

		// 1 1 1

		// 0 0 0

		assertSame(
				0,
				getNumberOfPaths(3, 3, new int[][] { { 0, 0, 0 }, { 1, 1, 1 },
						{ 0, 0, 0 } }));

		// 0 0

		// 0 1

		assertSame(0,
				getNumberOfPaths(2, 2, new int[][] { { 0, 0 }, { 0, 1 } }));

	}

	// @Test
	public void testNumberOfShortestPaths() {
		// 0 0
		// 0 0
		assertSame(
				2,
				getNumberofShortestPath(2, 2,
						new int[][] { { 0, 0 }, { 0, 0 } }));
		// 0 0
		// 1 0
		// 0 0

		// assertSame(1, getNumberofShortestPath(2, 3, new int[][] {{0, 0}, {1,
		// 0},{ 0, 0} }));
	}

}
